package a_doubleWrite;

import java.util.HashMap;
import java.util.Map;

/**
 * 输入：nums = [1,1,1,1,1], target = 3
 * 输出：5
 * 解释：一共有 5 种方法让最终目标和为 3 。
 * -1 + 1 + 1 + 1 + 1 = 3
 * +1 - 1 + 1 + 1 + 1 = 3
 * +1 + 1 - 1 + 1 + 1 = 3
 * +1 + 1 + 1 - 1 + 1 = 3
 * +1 + 1 + 1 + 1 - 1 = 3
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-08-04 19:54
 */
public class L494 {
    /*
    int count = 0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, target, 0);
        return count;
    }

    public void dfs(int[] nums, int target, int index) {
        if (index == nums.length) {
            if (target == 0) {
                count++;
                return;
            }
        }
        target -= nums[index];
        dfs(nums, target, index + 1);
        target += nums[index];

        target += nums[index];
        dfs(nums, target, index + 1);
        target -= nums[index];
    }
    */

    //记忆法递归
    Map<String, Integer> map = new HashMap<>();

    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, target, 0);
    }

    //需要有返回值
    public int dfs(int[] nums, int target, int index) {
        if (index == nums.length) {
            if (target == 0) return 1;//个数+1
            return 0;
        }
        String key = index + "-" + target;
        if (map.get(key) != null) {
            return map.get(key);
        }
        //递归
        int ans = dfs(nums, target - nums[index], index + 1)
                + dfs(nums, target + nums[index], index + 1);
        map.put(key, ans);
        return ans;
    }
}
